剑指Offer题解 - Day30

剑指 Offer 12. 矩阵中的路径

力扣题目链接 (opens new window)

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• board 和 word 仅由大小写英文字母组成

思路：

根据题目描述，可以看出是典型的矩阵搜索问题，因此考虑使用DFS进行处理。首先给出具体的代码，然后具体分析。

DFS

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
const dfs = (board, word, i, j, k) => {
    if (i >= board.length || i < 0
    || j >= board[0].length || j < 0 
    || board[i][j] !== word[k]) return false;
    if (k === word.length - 1) return true;
    board[i][j] = '';
    let result = dfs(board, word, i + 1, j, k + 1)
       || dfs(board, word, i - 1, j, k + 1) 
       || dfs(board, word, i, j + 1, k + 1) 
       || dfs(board, word, i, j - 1, k + 1)
  board[i][j] = word[k];
    return result;
}

const exist = (board, word) => {
    let words = word.split(''); // 分割字符串为数组
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (dfs(board, words, i, j, 0)) return true; // 调用DFS进行查找
        }
    }
    return false; // 没找到最终返回false
};

• 时间复杂度 O(mn)。
• 空间复杂度 O(mn)。

分析：

首先，先来看exist主函数。将字符串分割为字符组成的数组，方便搜索时进行比较。由于矩阵的大小是m * n ，因此需要每个节点都进行搜索。这里嵌套两层循环来搜索每个矩阵的节点。

接下来看DFS函数。既然是递归，那我们就应该找到递归的终止条件，这里的终止条件一共有四个，分别是：

• 行或者列的索引越界；
• 当前节点与需要查找的字符不相等；
• 当前节点已经访问过，因为将访问的节点重置为空字符，因此判断条件也是不相等。
• 当查找到字符数组的最后一个索引也没有终止时，意味着查找成功。此时是匹配成功的条件，返回true 。

当上述条件都不满足时，意味着查找正在进行中，没有触发终止的条件。此时将矩阵中的节点重置为空字符串，防止重复访问。

然后分别深度搜索当前节点的上下左右进行递归查找。最终查找成功或失败进行回溯时，将当前字符赋值为原来的值。最终返回布尔值结果，此时会走到主函数的if判断里，做相应的处理。

总结

本题考查搜索与回溯的算法。在搜索的过程中，通过||运算符进行剪枝处理并提前返回，防止无效的判断。搜索时需要处理边界条件与终止条件。

复杂度方面，矩阵中有m * n 个节点，因此空间复杂度是O(mn) ；最坏情况下，递归的深度是m * n ，因此时间复杂度是O(mn) 。